#include <iostream>
#include <array>
#include <vector>

using IDCard = std::array<int, 18>;

class Solution
{
public:
    void print(const IDCard &id, const std::vector<int> &tmp)
    {
        for (size_t i = 0, j = 0; i < id.size(); ++i)
        {
            if (id[i] == -1)
            {
                std::cout << tmp[j++];
            }
            else
            {
                std::cout << id[i];
            }
        }
        std::cout << std::endl;
    }

    void dfs(const IDCard &id, int level, std::vector<int> &temp)
    {
        if (level == 3)
        {
            int ssum = 0;
            for (size_t i = 0; i < 3; ++i)
            {
                ssum += temp[i] * idWeight_[14 + i];
            }
            if ((ssum + sum) % 11 == target)
            {
                print(id, temp);
                count += 1;
            }
            return;
        }

        if (id[14 + level] == -1)
        {
            for (int i = 0; i < 10; ++i)
            {
                temp.push_back(i);
                dfs(id, level + 1, temp);
                temp.pop_back();
            }
        }
        else
        {
            temp.push_back(0);
            dfs(id, level + 1, temp);
            temp.pop_back();
        }
    }
    int getIds(const IDCard &id)
    {
        for (int i = 0; i < idRef_.size(); ++i)
        {
            if (id[17] == idRef_[i])
            {
                target = i;
            }
        }
        for (size_t i = 0; i < 14; ++i)
        {
            sum += id[i] * idWeight_[i];
        }
        std::vector<int> temp;
        dfs(id, 0, temp);
        return count;
    }

private:
    const std::array<int, 17> idWeight_{7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
    const std::array<int, 11> idRef_{1, 0, -1, 9, 8, 7, 6, 5, 4, 3, 2};
    int count{0};
    int target{0};
    int sum{0};
};

int main(int argc, char **argv)
{
    Solution s;
    IDCard id1 = {4, 4, 0, 3, 0, 1, 1, 9, 6, 0, 0, 7, 1, 6, -1, -1, -1, 2};
    auto ans = s.getIds(id1);
    std::cout << "total cnt = " << ans << std::endl;
    return 0;
}
